%% Author: zhangjun
%% Created: 2009-4-6
%% Description: btree is binary tree, not is B tree or B+ tree
-module(btree).

%%
%% Include files
%%

%%
%% Exported Functions
%%
-export([start/0,push/1,member/2,info/1]).
-record(elem,{value,left,right}).
%%
%% API Functions
%%

%%
%% TODO: Add description of start/function_arity
%%
start() -> 
	Source = [3,2,1,4,7,5,6],
	Source1 = lists:map( fun(E)-> #elem{value=E} end, Source),
	push(Source1).

push([Head|Rest]) ->
	push(Head,Rest);
push(_Other) ->
	error.

push(Elem,[]) ->
	Elem;
push(Elem,[Head|Rest]) ->
	push( push(Elem,Head), Rest );
%%no way to do tail recursion
push(#elem{value=Value,left=Left,right=Right}=Elem, #elem{value=Value1}=Elem1) ->
	case Value > Value1 of
		true ->
			NewLeft = push(Left,Elem1),
			Elem#elem{left=NewLeft};		
		false ->
			NewRight = push(Right,Elem1),
			Elem#elem{right=NewRight}
	end;
push(undefined,Elem) ->
	Elem.
	

% Is X an element of a binary search tree?
member(_, undefined) -> false;
member(X, #elem{value=X}) -> true;
member(X, #elem{value=Value, left=Left, right=Right}) ->
	case X < Value of 
		true -> member(X, Left);
		false -> member(X, Right)
	end.

info(#elem{value=_V,left=Left,right=Right}) ->
	io:format("left tree elems is ~p~n", [number(Left)]),
	io:format("right tree elems is ~p~n", [number(Right)]),
	ok.

number(undefined) ->
	0;
number(#elem{value=_V,left=_Left,right=_Right}=HeadElem) ->
	%%1+number(Left) + number(Right).
	number(0,HeadElem).

number(Num, #elem{value=_V,left=Left,right=Right}) ->
	NewNum = number(Num+1, Left),
	number(NewNum,Right);
number(Num,undefined) ->
	Num.
	
	

%%
%% Local Functions
%%

